// https://leetcode.cn/problems/partition-list/description/?envType=study-plan-v2&envId=top-interview-150

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* less = new ListNode(0);
        ListNode* lessCur = less;
        ListNode* larger = new ListNode(0);
        ListNode* largerCur = larger;
        ListNode* curr = head;

        while (curr) {
            if (curr->val < x) {
                lessCur->next = curr;
                lessCur = lessCur->next;
            } else {
                largerCur->next = curr;
                largerCur = largerCur->next;
            }
            curr = curr->next;
        }
        largerCur->next = nullptr;
        lessCur->next = larger->next;
        return less->next;
    }
};